package com.jn.algorithm.alibaba.year2021.question1;

import java.sql.Connection;
import java.util.*;

/**
 * @author 江南大学1033190417
 * @date 2022/5/23 19:00
 */
public class Solution {

    private int count = Integer.MAX_VALUE;

    public int minMoney(int[] arr, int aim) {
        Arrays.sort(arr);
        dfs(arr, aim, 0,new StringBuilder());
        return count;
    }

    public void dfs(int[] arr, int aim, int cur,StringBuilder path) {
        if (cur == aim) {
            count=Math.min(count,path.length());
            return;
        }
        if (cur > aim) {
            return;
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            path.append(i);
            dfs(arr, aim, cur + arr[i],path);
            path.deleteCharAt(path.length()-1);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{5, 2, 3};
        System.out.println(solution.minMoney(nums, 20));
    }
}
